package developer.算法.链表.删除链表倒数第n个节点;

/**
 * @author zhangyongkang
 * @time 2025/3/20 16:00
 * @description 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * ：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 */
public class ShanChuLianBiaoDaoShuDiNGeJieDian {
    public static void main(String[] args) {
//        ListNode listNode = removeNthFromEnd(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))),
//                1);

        Solution3 solution3 = new Solution3();
        ListNode listNode = solution3.removeNthFromEnd(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))),
                5);

        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    static class Solution3 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode hair = new ListNode(0, head);
            dfs(hair, n);
            return head.next;
        }

        private int dfs(ListNode node, int n) {
            if (node == null) {
                return n;
            }
            if (n == 0) {
                node.next = node.next.next;
                return n;
            }
            return dfs(node.next, n) - 1;
        }


    }

    public static ListNode doRemove3(ListNode node, int n) {
        ListNode listNode = new ListNode();
        removeLastNNode3(listNode, node, n);
        if (listNode.next != null) {
            return listNode.next;
        } else {
            return node;
        }
    }

    public static int removeLastNNode3(ListNode lastNode, ListNode node, int n) {
        if (node == null) {
            return n;
        }
        int val = removeLastNNode3(node, node.next, n) - 1;
        if (val == 0) {
            lastNode.next = node.next;
        }

//        System.out.println("val" + val + " nodeVal" + node.val);
        return val;
    }


    public static ListNode removeNthFromEnd(ListNode head, int n) {
        int total = removeNode(head, 0, n);
        if (total == n) {
            return head.next;
        }
        return head;
    }

    private static int removeNode(ListNode head, int val, int target) {
        if (head == null) {
            return val;
        }
        int i = removeNode(head.next, val, target);
        if (i == target) {
            if (head.next != null) {
                head.next = head.next.next;
            }
        }
        return i + 1;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
